package leetcode.hot100;

import leetcode.common.ListNode;

import java.util.List;

@SuppressWarnings("all")
public class _19_删除链表的倒数第N个结点 {

    // 要求用一次遍历解决，即时间复杂度为O(n)
    // head = [1,2,3,4,5], n = 2 删除后为 [1,2,3,5]
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        // 慢指针
        ListNode slowNode = dummyNode;
        // 快指针
        ListNode fastNode = head;
        // 删除倒数第2个结点，要保证快指针比慢指针快3步(在有虚拟头结点的前提下)
        // 删除倒数第n和结点，要保证快指针比慢指针快(n+1)步
        for (int i = 0; i < n; i++) {
            fastNode = fastNode.next;
        }
        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        // 快->null 慢->3
        slowNode.next = slowNode.next.next;
        return dummyNode.next;
    }
}
